package com.yileiqian.alg;

public class LongestIncreaseSubArray {

	public static int DP1(int[] array) {
		int[] LIS = new int[array.length];
		for (int i = 0; i < array.length; i++) {
			LIS[i] = 1;
			for (int j = 0; j < i; j++) {
				if (array[j] < array[i] && LIS[i] < LIS[j] + 1) {
					LIS[i] = LIS[j] + 1;
				}
			}
		}
		
		int max = array[0];
		for(int i = 1; i < array.length;i++){
			if(LIS[i] > max){
				max = LIS[i];
			}
		}
		return max;
	}

	public static void main(String args[]) {
		int[] array = { 1, -1, 2, -3, 4, -5, 6, -7 };
		System.out.println(DP1(array));
	}
}
